// 使用栈来模拟实现队列
// 队列的功能为: 先入先出,与栈的功能相反(后入先出)
// 但是,我们可以使用两个栈来实现队列的功能
// 将一个栈作为入队栈,再将一个栈作为出队栈
// 当入队的时候,我们就入在入队栈里面
// 当出队的时候,将入队栈里面的所有数据以后入先出的方式压入出队栈里面
// 此时数据的顺序就变为: 最早的数据在最上面,最新的数据在最下面
// 我们此时出出队栈的数据就可以变成队列的功能了

typedef int STDataType ;

typedef struct Stack
{

    STDataType* arr ;

    int top ; // 指向栈顶的位置

    int capacity ; // 栈的容量

} ST ;

void StackInit (ST* ps)
{

    ps -> arr = NULL ;

    ps -> top = ps -> capacity = 0 ;

}

// 栈的销毁

void StackDestory (ST* ps)
{

    if (ps -> arr)
    {

        free (ps -> arr) ;

    }
    
        ps -> arr = NULL ;

        ps -> top = ps -> capacity = 0 ;

}

// 栈是否为空

bool StackEmpty (ST* ps)
{

    assert (ps) ;

    return ps -> top == 0 ;

}

// 入栈---从栈顶

void StackPush (ST* ps , STDataType x)
{

    assert (ps) ;

    if (ps -> top == ps -> capacity)

    {

        // 增容

        int newcapacity = ps -> capacity == 0 ? 4 : 2 * ps -> capacity ;

        STDataType* tmp = (STDataType*) realloc (ps -> arr , newcapacity * sizeof (STDataType)) ;

        if (tmp == NULL)
        {

            perror ("realloc fail!") ;

            exit (1) ;

        }

        ps -> arr = tmp ;

        ps -> capacity = newcapacity ;

    }

    ps -> arr [ps -> top++] = x ;

}

// 出栈---从栈顶

void StackPop (ST* ps)
{

    assert (!StackEmpty (ps)) ;

    --ps -> top ;

}

// 取栈顶元素

STDataType StackTop (ST* ps)
{

    assert (!StackEmpty (ps)) ;

    return ps -> arr [ps -> top - 1] ;

}

// 获取栈中有效元素个数

int StackSize (ST* ps)
{

    return ps -> top ;
    
}


typedef struct 
{

    ST s1 ; // 这里作为入队栈 pushST

    ST s2 ; // 这里作为出队栈 popST
    
} MyQueue;


MyQueue* myQueueCreate() 
{

    MyQueue* newqueue = (MyQueue*) malloc (sizeof (MyQueue)) ;

    StackInit (&(newqueue -> s1)) ;

    StackInit (&(newqueue -> s2)) ;

    return newqueue ;
    
}

void myQueuePush(MyQueue* obj, int x) 
{

    // 往pushST中插入数据
    
    StackPush (&(obj -> s1) , x) ;

}

// 检查popST是否为空
// (1): 不为空,直接出popST栈顶
// (2): 为空,pushST数据导入到popST中,再出popST栈顶

int myQueuePop(MyQueue* obj) 
{

    if (StackEmpty (&(obj -> s2)))
    {

        // 导数据

        while (!StackEmpty(&(obj -> s1)))
        {

            int tmp = StackTop (&(obj -> s1)) ;

            StackPop (&(obj -> s1)) ;

            StackPush (&(obj -> s2) , tmp) ;

        }

    }

    int tmp = StackTop (&(obj -> s2)) ;

    StackPop (&(obj -> s2)) ;

    return tmp ;
    
}

int myQueuePeek(MyQueue* obj) 
{

    if (StackEmpty (&(obj -> s2)))
    {

        // 导数据

        while (!StackEmpty (&(obj -> s1)))
        {

            int tmp = StackTop (&(obj -> s1)) ;

            StackPop (&(obj -> s1)) ;

            StackPush (&(obj -> s2) , tmp) ;

        }

    }

    int tmp = StackTop (&(obj -> s2)) ;

    return tmp ;
    
}

bool myQueueEmpty(MyQueue* obj) 
{

    return StackEmpty (&(obj -> s1)) && StackEmpty (&(obj -> s2)) ;
    
}

void myQueueFree(MyQueue* obj) 
{

    StackDestory (&(obj -> s1)) ;

    StackDestory (&(obj -> s2)) ;

    free (obj) ;

    obj = NULL ;
    
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/